翻訳と辞書 Words near each other ・ Horton College ・ Horton Country Park ・ Horton Court ・ Horton Creek ・ Horton Creek (Arizona) ・ Horton Creek (Oxbow Creek) ・ Horton Creek (Tunkhannock Creek) ・ Horton cum Peel ・ Horton D. Haight ・ Horton family ・ Horton Fieldhouse ・ Horton Foote ・ Horton General Hospital ・ Horton Glacier ・ Horton Grand Hotel ・ Horton graph ・ Horton Gristmill ・ Horton Group ・ Horton Grove ・ Horton H. Hobbs, Jr. ・ Horton Hatches the Egg ・ Horton Hatches the Egg (1942 film) ・ Horton Hears a Who! ・ Horton Hears a Who! (disambiguation) ・ Horton Hears a Who! (film) ・ Horton Hears a Who! (TV special) ・ Horton Heath ・ Horton Heath, Dorset ・ Horton Heath, Hampshire ・ Horton High School Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Horton graph ： ウィキペディア英語版 Horton graph In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.〔Tutte, W. T. "On the 2-Factors of Bicubic Graphs." Disc. Math. 1, 203-208, 1971/72.〕〔Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.〕 After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two Ellingham-Horton graphs (54 and 78 vertices).〔Horton, J. D. "On Two-Factors of Bipartite Regular Graphs." Disc. Math. 41, 35-41, 1982.〕〔Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.〕 The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78.〔Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.〕 At that time, it was the smallest know counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54.〔Ellingham, M. N. and Horton, J. D. "Non-Hamiltonian 3-Connected Cubic Bipartite Graphs." J. Combin. Th. Ser. B 34, 350-353, 1983.〕 No smaller non-hamiltonian cubic 3-connected bipartite graph is currently known. As a non-hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.〔V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf "An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs" (arXiv:math/0610779v1 ).〕 The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10 and girth 6. It is also a 3-edge-connected graph. ==Algebraic properties== The automorphism group of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×''S''4, the direct product of the Klein four-group and the symmetric group ''S''4. The characteristic polynomial of the Horton graph is : $(x-3)\; (x-1)^\; x^4\; (x+1)^\; (x+3)\; (x^2-5)^3\; (x^2-3)^(x^2-x-3)\; (x^2+x-3)$ $(x^-23\; x^8+188\; x^6-644\; x^4+803\; x^2-101)^2$ $(x^-20\; x^8+143\; x^6-437\; x^4+500\; x^2-59)$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Horton graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.